/*
 * @lc app=leetcode.cn id=954 lang=cpp
 *
 * [954] 二倍数对数组
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <stdlib>
#include <string>
#include <string.h>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cmath>

using namespace std;
// @lc code=start
class Solution {
public:
    bool canReorderDoubled(vector<int>& arr) {
    //哈希表+排序
        unordered_map<int, int> cnt;
        for (int x : arr) {
            cnt[x]++;
        }
        //对0单独讨论
        if (cnt[0] % 2) {
            return false;
        }
        vector<int> vals;
        vals.reserve(cnt.size());
        for (auto &x : cnt) {
            vals.push_back(x.second);
        }
        sort(vals.begin(), vals.end(), [](int a, int b) { return abs(a) < abs(b); });

        for (int x : vals) {
            if (cnt[2 * x] < cnt[x]) { // 无法找到足够的 2x 与 x 配对
                return false;
            }
            cnt[2 * x] -= cnt[x];
        }
        return true;
    }
};
// @lc code=end

// bool canReorderDoubled(vector<int>& arr) {
//         priority_queue<int,vector<int>,greater<int>> q;
//         sort(arr.begin(),arr.end());
//         for(int x : arr) {
            //正负分开讨论
//             if(x < 0) {
//                 if(!q.empty() && x == double(q.top())/2.0) {
//                     q.pop();
//                 }else {
//                     q.push(x);
//                 }
//             }else {
//                 if(!q.empty() && x == q.top()*2) {
//                     q.pop();
//                 }else {
//                     q.push(x);
//                 } 
//             }
//         }
//         return q.empty();
//     }
